Collection of Tools & Utilities/Collection of Tools and Utilities.iso/graphic/rtnews.zip/RTNV5N3

Internet Message Format | 1992-09-13 | 40KB

From nucsrl!news.acns.nwu.edu!zaphod.mps.ohio-state.edu!cis.ohio-state.edu!rutgers!psinntp!psinntp!eye!erich Mon Sep  7 19:44:41 CDT 1992
Article: 13391 of comp.graphics
Path: nucsrl!news.acns.nwu.edu!zaphod.mps.ohio-state.edu!cis.ohio-state.edu!rutgers!psinntp!psinntp!eye!erich
From: [e-mail] (Eric Haines)
Newsgroups: comp.graphics
Subject: Ray Tracing News, Volume 5, Number 3
Summary: point in polygon revisited
Message-ID: <[e-mail]>
Date: 2 Sep 92 14:16:09 GMT
Sender: [e-mail] (Eric Haines)
Organization: 3D/EYE, Inc.  Ithaca, NY
Lines: 1000


 _ __                 ______                         _ __
' )  )                  /                           ' )  )
 /--' __.  __  ,     --/ __  __.  _. o ____  _,      /  / _  , , , _
/  \_(_/|_/ (_/_    (_/ / (_(_/|_(__<_/ / <_(_)_    /  (_</_(_(_/_/_)_
             /                               /|
            '                               |/

            "Light Makes Right"

             September 2, 1992
            Volume 5, Number 3

Compiled by Eric Haines, 3D/Eye Inc, 2359 Triphammer Rd, Ithaca, NY 14850
    [e-mail]
All contents are copyright (c) 1992 by the individual authors
Archive locations: anonymous FTP at princeton.edu (128.112.128.1)
    /pub/Graphics/RTNews, wuarchive.wustl.edu:/graphics/graphics/RTNews,
    and many others.
UUCP archive access: write Kory Hamzeh (quad.com!avatar!kory) for info.

Contents:
    Introduction
    Intersection Between a Line and a Polygon (UNDECIDABLE??), by Dave Baraff,
    Tom Duff
    Fastest Point in Polygon Test, by Aladdin Nassar, Philip Walden, Eric
    Haines, Tom Dickens, Ron Capelli, Sundar Narasimhan, Christopher Jam,
    and (last but not least) Stuart MacMartin
    Polygon Intersection via Barycentric Coordinates, by Peter Shirley
    Many-Sided Polygon Intersection, by Eric Haines, Benjamin Zhu
    Code for Point in Polygon Intersectors, by Eric Haines

-------------------------------------------------------------------------------

Introduction

This special issue is dedicated to everyone's (well, at least my) favorite
computer graphics FAQ:  how do you find if a given point is inside a polygon?
John Griegg's FAQ posting points at _An Introduction to Ray Tracing_, edited
by Andrew Glassner.  This issue speeds up that algorithm (count the crossings
of a test ray), and hopefully lays to rest the idea of using the "sum the
angles" algorithm.  Plus there's a little discussion of what to do for special
cases such as triangles and complex polygons, and code for four different ways
to do this test at the end of the issue.

-------------------------------------------------------------------------------

[To begin this issue, here is one of the better pieces of obfuscatory writing
in the field of computer graphics.  Reprinted from RTNews8 - EAH]


Intersection Between a Line and a Polygon (UNDECIDABLE??),
    by Dave Baraff, Tom Duff

    From: [e-mail]
    Newsgroups: comp.graphics
    Keywords: P, NP, Jordan curve separation, Ursyhon Metrization Theorem
    Organization: Program of Computer Graphics

In article [...] [e-mail] (Timothy Lyle Smith) writes:
>
>  I need to find a formula/algorithm to determine if a line intersects
>  a polygon.  I would prefer a method that would do this in as little
>  time as possible.  I need this for use in a forward raytracing
>  program.

I think that this is a very difficult problem.  To start with, lines and
polygons are semi-algebraic sets which both contain uncountable number of
points.  Here are a few off-the-cuff ideas.

First, we need to check if the line and the polygon are separated.  Now, the
Jordan curve separation theorem says that the polygon divides the plane into
exactly two open (and thus non-compact) regions.  Thus, the line lies
completely inside the polygon, the line lies completely outside the polygon,
or possibly (but this will rarely happen) the line intersects the polyon.

Now, the phrasing of this question says "if a line intersects a polygon", so
this is a decision problem.  One possibility (the decision model approach) is
to reduce the question to some other (well known) problem Q, and then try to
solve Q.  An answer to Q gives an answer to the original decision problem.

In recent years, many geometric problems have been successfully modeled in a
new language called PostScript.  (See "PostScript Language", by Adobe Systems
Incorporated, ISBN # 0-201-10179-3, co. 1985).

So, given a line L and a polygon P, we can write a PostScript program that
draws the line L and the polygon P, and then "outputs" the answer.  By
"output", we mean the program executes a command called "showpage", which
actually prints a page of paper containing the line and the polygon.  A quick
examination of the paper provides an answer to the reduced problem Q, and thus
the original problem.

There are two small problems with this approach.

    (1) There is an infinite number of ways to encode L and P into the
    reduced problem Q.  So, we will be forced to invoke the Axiom of
    Choice (or equivalently, Zorn's Lemma).  But the use of the Axiom of
    Choice is not regarded in a very serious light these days.

    (2) More importantly, the question arises as to whether or not the
    PostScript program Q will actually output a piece of paper; or in
    other words, will it halt?

    Now, PostScript is expressive enough to encode everything that a
    Turing Machine might do; thus the halting problem (for PostScript) is
    undecidable.  It is quite possible that the original problem will turn
    out to be undecidable.


I won't even begin to go into other difficulties, such as aliasing, finite
precision and running out of ink, paper or both.

A couple of references might be:

1. Principia Mathematica.  Newton, I.  Cambridge University Press, Cambridge,
   England.  (Sorry, I don't have an ISBN# for this).

2. An Introduction to Automata Theory, Languages, and Computation.  Hopcroft, J
  and Ulman, J.

3. The C Programming Language. Kernighan, B and Ritchie, D.

4. A Tale of Two Cities. Dickens, C.

--------

From: [e-mail] (Tom Duff)
Summary: Overkill.
Organization: AT&T Bell Laboratories, Murray Hill NJ

The situation is not nearly as bleak as Baraff suggests (he should know
better, he's hung around The Labs for long enough).  By the well known
Dobbin-Dullman reduction (see J. Dullman & D. Dobbin, J. Comp. Obfusc.
37,ii:  pp. 33-947, lemma 17(a)) line-polygon intersection can be reduced to
Hamiltonian Circuit, without(!) the use of Grobner bases, so LPI (to coin an
acronym) is probably only NP-complete.  Besides, Turing-completeness will no
longer be a problem once our Cray-3 is delivered, since it will be able to
complete an infinite loop in 4 milliseconds (with scatter-gather.)

--------

From: [e-mail] (David Baraff)

Well, sure it's no worse than NP-complete, but that's ONLY if you restrict
yourself to the case where the line satisfies a Lipschitz condition on its
second derivative.  (I think there's an '89 SIGGRAPH paper from Caltech that
deals with this).

-------------------------------------------------------------------------------

Fastest Point in Polygon Test, by Aladdin Nassar, Philip Walden, Eric Haines,
    Tom Dickens, Ron Capelli, Sundar Narasimhan, Christopher Jam, and
    (last but not least) Stuart MacMartin


Aladdin Nassar asked a variant on the classic question:

What is the MOST EFFICIENT way to find if a point lies within a SIMPLE
polygon given a set of vertices (in no particular order) and the point
coordinate ?   Are there anonymous ftp sites with such canned functions
instead of re-inventing the wheel.  Excuse me if that is a trivial question.

----

Philip Walden ([e-mail]) replies:

Another alternative to using a test ray is to sum the arc angles from
the vertices to the test point. If the sum is 2pi, the point is inside,
if 0 it's outside. i.e.

    give a polygon with a set of vertices v[1:n] an test point p

    if (SUM i=1 to n (arcangle(v[i]->p->v[i+1])) > pi
    then p is inside